package linkedtable;

/**
 * @Description 剑指 Offer II 022. 链表中环的入口节点
 * @Author Firenut
 * @Date 2023-04-30 11:05
 */
public class TII022_detectCycle {
    /**
     * 一些推算出来的规律:
     *  设有环链表中,head到环入口的长度为a,环的长度为b
     *  快慢指针第一次相遇的时候,快指针走过的长度为f,慢指针走过的长度为s,则 f = 2*s (因为快指针每次移动的距离是慢指针的2倍)
     *  快指针走过的距离 f = 2nb, 慢指针走过的距离为 s = nb
     *  而走到链表环入口结点的步数为 a + nb
     *  所以要让慢指针到达入口结点，还需要移动a个结点的位置
     *  此时就可以再用一次双指针，让fast指针从head开始移动,当fast移动a个距离之后，fast和slow就相遇了
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (true) {
            if (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            } else {
                return null;
            }
            if (fast == slow) {
                fast = head;
                break;
            }
        }
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
